package com.zsjt.basic.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Auther ZhanBo
 * @Date 2020/5/19
 */
public class SelectSort {

    public static void main(String[] args) {
        int array[] ={3,9,-1,10,0};
        sort(array);
        System.out.println(Arrays.toString(array));
        //test(100000);
    }
    /**
     * 选择排序
     * 思想：先找到数据中的最小值，放在第一位。依次找出数据最小值，执行数据长度-1次
     */
    public static void sort(int array[]){
        int minIndex=0;//定义最小值的索引位置
        int min = 0;//假设第i个是最小值
        for (int i = 0 ; i < array.length-1 ; i++){
             minIndex = i;
             min = array[i];
            for (int j = i + 1 ; j < array.length ; j++){
                if (min > array[j]){ //如果第一个不是最小值，则进行最小值赋值和索引改变
                    min = array[j];
                    minIndex =j;
                }
            }
            if(minIndex!=i){    //最小值的索引未改变
                array[minIndex] = array[i]; //把最小值移到当前索引
                array[i] =min; //把最小值移到当前索引
            }
            //System.out.println("第"+(i+1)+"趟"+ Arrays.toString(array));
        }
    }

    /**
     * 测试选择排序
     * @param n
     */
    public static void test(int n){
        //测试冒泡排序O(n^2)的速度，给80000个数据
        int arr [] = new int [n];
        for (int i =0 ;i<arr.length;i++)
            arr[i] = (int) (Math.random()*n);

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        System.out.println("排序前"+simpleDateFormat.format(date1));

        sort(arr);

        Date date2 = new Date();
        System.out.println("排序后"+simpleDateFormat.format(date2));
    }
}
